/*
 * @lc app=leetcode.cn id=120 lang=javascript
 *
 * [120] 三角形最小路径和
 */

// @lc code=start
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
  const n = triangle.length;
  const curMin = Array.from({ length: n }, () => new Array(n).fill(0));
  // 最后一层赋值
  for (let x = 0; x < n; x++) {
    curMin[n - 1][x] = triangle[n - 1][x];
  }

  // 从底向上计算
  for (let i = n - 2; i >= 0; i--) {
    for (let j = i; j >= 0; j--) {
      curMin[i][j] =
        triangle[i][j] + Math.min(curMin[i + 1][j], curMin[i + 1][j + 1]);
    }
  }
  return curMin[0][0];
};
// @lc code=end
